package selectionSort;

public class ReversedSelectionSort {
    public static <E extends Comparable<E>> void sort(E[] data) {
        //循环不变量：[0,i)为乱序，[i,n)为有序。
        //注意这里“有序”的含义。有序是指[i,n)是整个数组中最大的几个元素。
        //之前写成了 i=data.length-1开始，因此最后一个数据没有参与排序。这不同于插入排序。
        //插入排序可以默认最后一个是有序的。
        for (int i = data.length ; i > 0; i--) {
            int minIndex = i - 1;
            //找出[0,i)中最小的一个。初始化为i-1。
            for (int j = i - 1; j >= 0; j--)
                if (data[minIndex].compareTo(data[j]) < 0)
                    minIndex = j;
            swap(data, minIndex, i - 1);
        }
    }

    public static <E> void swap(E[] data, int i, int j) {
        E tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    public static void main(String[] args) {
        int n = 1000;
        Integer[] data = ArrayGenerator.generateRandomArray(n, n);
        SortingHelper.sortTest("ReversedSelectionSort",data);
        System.out.println("ReversedSelectionSort ok.");
    }
}
